/*
  基数排序: 
    将整数按位数切割成不同的数字, 然后按每个位数分别比较
  最低位排序: 
    先从最低位开始排序, 再对次低位排序, 直到对最高位排序后得到一个有序序列;
*/
var arr = [2, 5, 3, 7, 6, 4, 21, 13, 1]
var counter = []
function radixSort (arr, maxDigit) {
  var mod = 10
  var dev = 1
  for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (var j = 0; j < arr.length; j++) {
      var bucket = parseInt((arr[j] % mod) / dev)
      if (counter[bucket] == null) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    var pos = 0
    for (var j = 0; j < counter.length; j++) {
      var value = null
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value
        }
      }
    }
  }
  return arr
}
console.log(radixSort(arr, 2))
